package com.zlk.algorithm.huawei.nowcoder.string;

import java.io.*;
import java.util.Scanner;

/**
 * @program: algorithm
 * @ClassName HJ32
 * @description:
 * Catcher是MCA国的情报员，他工作时发现敌国会用一些对称的密码进行通信，比如像这些
 * "ABBA"
 * "ABA"
 * "A"
 * "123321"
 *
 *   ABAB
 *
 * 但是他们有时会在开始或结束时加入一些无关的字符以防止别国破解。比如进行下列变化
 * "ABBA"→"12ABBA" 、
 * "ABA"→"ABAKK"，
 * "123321"→"51233214" 。因为截获的串太长了，而且存在多种可能的情况（
 * "abaaab" 可看作是
 * "aba" 或
 * "baaab" 的加密形式），Cathcer的工作量实在是太大了，他只能向电脑高手求助，你能帮Catcher找出最长的有效密码串吗？
 *
 *
 * dp 题意解答就是找出最长回文字串
 * @author: slfang
 * @create: 2024-12-24 16:51
 * @Version 1.0
 **/
public class HJ32 {

    public static final int MAXN = 2500;
    public static int[][] dp = new int[MAXN][MAXN];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        //System.out.println(solution(s));
        System.out.println(fDp(s));
    }



    //最长回文子串的中心扩散法，遍历每个字符作为中间位，进行左右比较
    private static int solution(String s) {
        int res = 0;
        for(int i = 0; i < s.length(); i++) {
            // ABA型
            int len1 = longest(s, i, i);
            // ABBA型
            int len2 = longest(s, i, i + 1);
            res = Math.max(res, len1 > len2 ? len1 : len2);
        }
        return res;
    }

    private static int longest(String s, int l, int r) {
        while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            l--;
            r++;
        }
        return r - l - 1;
    }

    //定义 dp 数组：字符串s的 i 到 j 索引位置的字符组成的子串是否为回文子串
    //状态转移: 如果左右两字符相等, 同时[l+1...r-1]范围内的字符是回文子串, 则 [l...r] 也是回文子串
    //状态转移的同时，不断更新对比的子串长度，最终确定最长回文子串的长度
    // dp[i][j] : s[i]==s[j] &dp[i+1][j-1]
    private static int fDp(String str) {
        int length = str.length();
        int ans = 1;
        boolean[][] dp = new boolean[length][length];
        for (int i = 0; i < length; i++) {
            dp[i][i]=true;
        }
        for (int i = length-1; i >=0; i--) {
            for (int j = i+1; j<length; j++) {
                if(str.charAt(i)==str.charAt(j)&&(i+1<length&&j-1>0)&&(j-i<2|dp[i+1][j-1])){
                    dp[i][j] = true;
                    ans = Math.max(j-i+1,ans);
                }
            }
        }
        return ans;
    }



}
